package leetcode_day._2023._12;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1466.重新规划路线
 * 算法: 深度优先搜素
 *
 * @author yezh
 * @date 2023/12/7 11:25
 */
public class _07 {

    int ans = 0;

    public int minReorder(int n, int[][] connections) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int[] connection : connections) {
            g[connection[0]].add(new int[]{connection[1], 1});
            g[connection[1]].add(new int[]{connection[0], 0});
        }
        dfs(0, -1, g);
        return ans;
    }

    void dfs(int cur, int fa, List<int[]>[] g) {
        for (int[] path : g[cur])
            if (path[0] != fa) {
                if (path[1] == 1) ++ans;
                dfs(path[0], cur, g);
            }
    }

}
